In particle beam therapy, one problem is to determine a path for the beam that takes the least amount of time, and delivers the prescribed dose. The problem is formulated as follows. Given a 3D planning target volume (PTV), discretized to a large number of 3D locations in the volume where the beam stops to deliver the dose, a path planner needs to find the path through the beam-stop locations, such that each location is traversed only once. Each location represents an approximate small cube (mm3) in a volume of tissue The 3D locations that are traversed by the ionized beam can be controlled horizontally by magnets arranged in the XY plane, and vertically by adjusting energy in the Z direction (depth). Due to physical constraints of the treatment equipment, change of the beam depth is relatively slow. Hence movement of the beam in the XY plane is preferred. Utilizing this observation, most conventional methods for path optimization reduce the complexity of the optimization task by treating each discrete slice of beam-stop locations independently of others, and only consider a set of 2D solutions, i.e., one per slice. This reduces the computational complexity of the task.
However, even slice-by-slice exact solution in a direct formulation for any realistic size of the problem (˜5,000-40,000 locations per slice) cannot be obtained in reasonable time. Several conventional methods determine the path for the beam using a well known traveling salesman problem (TSP). For example, some methods using a path planner that approximates the optimal path for the TSP problem. On the other hand, approximate solutions to the direct TSP formulation using a conventional TSP solver have the following disadvantages.
High Computational Complexity
The exact solution to the TSP has a complexity of O(n!). Thus, a realistic problem of several thousand locations takes a prohibitive amount of time. Approximate solutions can be obtained in polynomial time, which still can be unacceptably long.
Difficulty in Enforcing Path Constraints
The constraints in conventional traditional TSP solvers are usually expressed as a process of distance computation. The edge cost is determined such that every pair of nodes has some associated cost. Unfortunately, a path self-intersection constraint, important in radiation therapy, cannot be expressed using only pairs of nodes.
Accordingly, it is desired to reduce amount of computational time spend on determining the path of the particle beam through a 3D tissue volume.